package ch04.min_gengerate_tree;

import ch04.Edge;
import ch04.EdgeWeightGraph;

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class LazyPrimMST {
    private boolean[] marked;
    private Queue<Edge> mst;
    private PriorityQueue<Edge> pq;

    public LazyPrimMST(EdgeWeightGraph graph) {
        int v = graph.getV();
        marked = new boolean[v];
        mst = new LinkedList<>();
        pq = new PriorityQueue<>();
        visit(graph, 0);
        while (!pq.isEmpty()) {
            Edge edgePo = pq.poll();
            int vv = edgePo.either();
            int ww = edgePo.other(vv);
            if (marked[vv] && marked[ww]) {
                continue;
            }
            mst.add(edgePo);
            if (!marked[vv]) {
                visit(graph, vv);
            }
            if (!marked[ww]) {
                visit(graph, ww);
            }
        }
    }

    public void visit(EdgeWeightGraph graph, int s) {
        marked[s] = true;
        Iterable<Edge> adj = graph.adj(s);
        for (Edge edge : adj) {
            if (!marked[edge.other(s)]) {
                pq.offer(edge);
            }
        }
    }

    public Queue<Edge> getMst() {
        return mst;
    }

    public static void main(String[] args) {
        LazyPrimMST lpMST = new LazyPrimMST(EdgeWeightGraph.getGraph());
        for (Edge edge : lpMST.getMst()) {
            System.out.println(edge);
        }

    }


}
/*
        Edge{v=0, w=1, weight=7.8}
        Edge{v=1, w=9, weight=5.0}
        Edge{v=3, w=9, weight=4.0}
        Edge{v=1, w=2, weight=5.2}
        Edge{v=5, w=2, weight=2.0}
        Edge{v=4, w=5, weight=4.5}
        Edge{v=8, w=4, weight=1.5}
        Edge{v=7, w=2, weight=7.8}
        Edge{v=6, w=1, weight=9.0}*/
/*
        Edge{v=8, w=4, weight=1.5}
        Edge{v=5, w=2, weight=2.0}
        Edge{v=3, w=9, weight=4.0}
        Edge{v=4, w=5, weight=4.5}
        Edge{v=1, w=9, weight=5.0}
        Edge{v=1, w=2, weight=5.2}
        Edge{v=0, w=1, weight=7.8}
        Edge{v=7, w=2, weight=7.8}
        Edge{v=6, w=1, weight=9.0}*/
